package DoublePointers.Medium;

public class LC0011 {
    /**
     * 本题双指针的语义是：[left,right]范围内的任意两个竖线都有可能是最大容器的竖线。
     * 假设left向右移动，说明left与它右边的任意一个竖线所形成的容器都已经被考虑过。
     * 每次移动的指针p，是height[p]较小的p。如果两个指针的高度一样，则两个指针都移动。
     * 可以证明，这种算法能够覆盖整个解空间，从而得到全局最优解。
     * <p>
     * 证明方法：画三角矩阵，矩阵中的每个元素表示一种可能的组合，如元素(α,β)表示第α条竖线和第β条竖线是容器的边界；α≠β。
     * 由于对称性，(α,β)和(β,α)只需出现一个，矩阵应为上三角或下三角矩阵。
     * 每次有指针发生移动，就划去整行/整列的元素，表示对于任意γ，(α,γ)/(γ,β)都已被考虑。
     * 最后应发现能删除所有元素，表明能覆盖整个解空间。
     */
    public int maxArea(int[] height) {
        int N = height.length;
        int left = 0, right = N - 1;
        int maxArea = -1;

        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(area, maxArea);
            if (height[left] < height[right]) {
                left++; // 所有(left,p)，p∈[left+1,right-1]的对都已无需考虑，因为不可能大于先前算出的area
            }
            else if (height[left] > height[right]) {
                right--;
            }
            else {
                left++;
                right--;
            }
        }

        return maxArea;
    }
}
